package com.toutiao.model

import scala.collection.mutable.{HashMap => HMap}
import scala.collection.mutable.ArrayBuffer

import org.apache.log4j.Logger

class InvertIndex[T] {
  
  val _log = Logger.getLogger(this.getClass.getName)
  
  val M = new HMap[T, ArrayBuffer[Long]]
  
  def _binarySearch(zs:ArrayBuffer[Long], start:Int, len:Int, key:Long) = {
    var high = start+len
    var low  = start-1
    
    while (high - low > 1){
      val guess = (high+low)/2
      if (zs(guess) < key)
        low = guess
      else
        high = guess
    }
    
    high
  }
  
  def insert(n:Long, m:Array[T]) {
    for (v <- m){
      val zs = M.getOrElse(v, new ArrayBuffer[Long])
      if (zs.size == 0 || zs(zs.size-1) <= n){
        zs += n
      }
      else {
        val i = _binarySearch(zs,0,zs.size,n)
        zs.insert(i,n)
      }
      M(v) = zs
    }
  }
  
  def remove(n:Long, m:Array[T]) {
    for (v <- m if M.contains(v)){
      val zs = M(v)
      val i = _binarySearch(zs,0,zs.size,n)
      if (i >= 0 && i < zs.size){
        zs.remove(i)
      }
      else {
        _log.error(v+" "+M(v))
        _log.error(n+" "+v+" "+i)
      }
      if (zs.size == 0){
        M.remove(v)
      }
      else {
        M(v) = zs
      }
    }
  }
  
  
  def contains(z:T) = {
    M.contains(z)
  }
  
  def apply(z:T):ArrayBuffer[Long] = {
    M(z)
  }

}
